#include<iostream>
#include<vector>
using namespace std;

//复写零

void duplicateZeros(vector<int> &arr)
{
    int cur = 0;
    int dest = -1;

    // 先找到复写后的最后一个元素位置
    while (dest < (int)arr.size() - 1)
    {
        if (arr[cur])
        {
            dest += 1;
        }
        else
        {
            dest += 2;
        }
        if (dest < arr.size() - 1)
        {
            cur++;
        }
    }

    // 处理边界情况
    if (dest == arr.size())
    {
        arr[arr.size() - 1] = 0;
        cur--;
        dest -= 2;
    }

    while (cur >= 0)
    {
        // cur指针遇到非0元素，复写一次，两个指针都往前移动一次
        if (arr[cur])
        {
            arr[dest--] = arr[cur--];
        }
        // cur指针遇到0元素，复写两次，dest指针先移动一次，两个指针再一起移动一次
        else
        {
            arr[dest--] = 0;
            arr[dest--] = 0;
            cur--;
        }
    }
}

int main(){
    vector<int> arr = {1, 0, 2, 3, 0, 4, 5, 0};
    duplicateZeros(arr);
    for(auto e : arr){
        cout << e << " ";
    }
    cout << endl;
    return 0;
}